public class ReorderList {
    // 重排链表
    // https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=196&tqId=37046&rp=1&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page&difficulty=undefined&judgeStatus=undefined&tags=&title=
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            fast = fast.next.next;
            if (fast == null) {
                break;
            }
            slow = slow.next;
        }
        ListNode cur = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        cur = head;
        while (cur != null && prev != null) {
            ListNode curNext = cur.next;
            ListNode prevNext = prev.next;
            cur.next = prev;
            prev.next = curNext;
            cur = curNext;
            prev = prevNext;
        }
    }
}
